//和可被k整除的子数组
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        int n = nums.size();
        hash[0] = 1;
        int sum = 0 , ret = 0;
        for(size_t i = 0 ; i < n ; ++i)
        {
            sum += nums[i];
            int temp = ((sum % k) + k) % k;
            if(hash.count(temp)) ret += hash[temp];
            hash[temp]++;
        }
        return ret;
    }
};

//连续数组
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        for(auto& e : nums)
        {
            if(e == 0) e = -1;
        }
        //转化为和为0的最长子数组的长度
        unordered_map<int,int> hash; //sum：第一次出现的位置
        hash[0] = -1;
        int ret = 0 , sum = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            sum += nums[i];
            if(!hash.count(sum)) hash[sum] = i;
            ret = max(ret,i-hash[sum]);
        }

        return ret;   
    }
};

